package com.mdnote.jianzhi_offer.tree;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/11
 * @description 二叉树的下一个节点
 */
public class Offer08 {

    private static Node pre;

    public void threaderInOrder(Node root) {

        // 左子节点
        if (root.left != null) {
            threaderInOrder(root.left);
        }

        if (pre != null) {
            pre.next = root;
        }
        pre = root;

        if (root.right != null) {
            threaderInOrder(root.right);
        }
    }


    public Node getNext(Node node) {

        // 如果节点包含右子节点，那么下一个就是他的右子树的最左子节点
        if (node.right != null) {
            Node cur = node.right;
            while (cur.left != null) {
                cur =  cur.left;
            }
            return cur;
        }

        // 如果该节点是其父节点的左子节点，那下一个就是他的父节点
        if (node.parent != null && node.parent.left == node) {
            return node.parent;
        }

        // 如果该节点是其父节点的右子节点，下一个就只能顺着父节点向上找，知道找到
        if (node.parent != null && node.parent.right == node) {
            Node cur = node;
            while (cur.parent != null && cur == cur.parent.right) {
                cur = cur.parent;
            }
            return cur;
        }
        return null;
    }


    public static void main(String[] args) {
        Offer08 offer08 = new Offer08();

        Node root = new Node(10);
        root.left = new Node(9, root);
        root.right = new Node(11, root);

        System.out.println(offer08.getNext(root.left));
    }

    private static class Node {
        private int val;
        private Node left;
        private Node right;

        private Node parent;

        private Node next;

        public Node(int val) {
            this.val = val;
        }

        public Node(int val, Node parent) {
            this.val = val;
            this.parent = parent;
        }

        @Override
        public String toString() {
            return this.val + "";
        }
    }
}
